package OJPractice;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

/*
* 复习排序
* 稳定性：如果一个排序是稳定的，此时是可以变成不稳定的，但是如果这个排序是不稳定的，
* 此时是不可以变成稳定的排序的
* */
class test1 {
    // 有序数组
    public static void initArrayOrder(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
    }
    // 无序数组
    public static void initArrayNotOrder(int[] arr) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10_0000);
        }
    }

    // 逆序数组
    public static void initArrayReverseOrder(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr.length - i;
        }
    }

    public static void testInsertSort(int[] arr) {
        arr = Arrays.copyOf(arr, arr.length);
        long startTime = System.currentTimeMillis();
        SortPractice.insertSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("直接插入排序耗时：" + (endTime - startTime));
    }

    public static void main1(String[] args) {
        int[] arr = new int[10_0000];
        // initArrayOrder(arr);
        // initArrayNotOrder(arr);
        initArrayReverseOrder(arr);
        testInsertSort(arr);
    }

    public static void main2(String[] args) {
        int[] arr = {12, 56, 32, 67, 10, 19, 4};
        // int[] arr = new int[100_0000];
        // initArrayOrder(arr);
        SortPractice.insertSort2(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
//        long startTime = System.currentTimeMillis();
//        SortPractice.quickSort(arr);
//        long endTime = System.currentTimeMillis();
//        System.out.println("快速排序耗时：" + (endTime - startTime));
    }

    public static void main(String[] args) {
        // 测试归并排序
        int[] arr = {12, 56, 32, 67, 10, 19, 4};
        SortPractice.mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
public class SortPractice {
    // 插入排序
    // 过程 arr[1]元素放到tmp中，j下标控制数组前边的元素去和tmp中的值去比较
    // 如果比 tmp 中的值大，此时让所有大的值往后挪动即可
    /* 时间复杂度：O（N ^ 2）  最好时间复杂度：O（N）（也就是当数据接近有序的时候排序速度非常快）
       所以一般的场景就是数据基本有序的时候就用 插入排序
    * */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    // arr[j + 1] = tmp;
                    break;
                }
            }
            // 正常情况下，数组中最后一个元素是最小的，此时应该将这个元素放到最前边
            // 但是 j 下标是负数了，此时跳出循环了，所以就应该将tmp的最小值放到 j + 1 下标的位置上
            arr[j + 1] = tmp;
        }
    }


    // 希尔排序
    // 过程：缩小增量（分的组数越来越少）排序，分组排序，但是分组又是间隔式的分组，
    // 每次分组之后的排序过程就是插入排序 （所以也是插入排序的一种优化）
    // 时间复杂度：O（1.3）
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    private static void shell(int[] arr, int gap) {
        // 插入排序就是i从1的位置开始，分组之后，如：10个数据分两组，分组之后的下标就是 0 2 4...
        // 此时i 就是从2的位置开始，但是i不能 += gap，这样就只会排一组，如果是i++，此时所有分的组都可以被排序到
        // j 下标是 -= gap
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (tmp < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    arr[j + 1] = tmp;
                    break;
                }
                // 正常情况下，数组中最后一个元素是最小的，此时应该将这个元素放到最前边
                // 但是 j 下标是负数了，此时跳出循环了，所以就应该将tmp的最小值放到 j + 1 下标的位置上
                arr[j + 1] = tmp;
            }
        }
    }

    // 选择排序
    // 过程：如果有一个元素，此时的数组就是有序的，所以 j 下标从1开始，如果arr[j] < arr[i]，就每次从
    // 待排序的数组中选择一个最小的元素放到最前边
    // 时间复杂度：O（N ^ 2）
    // 稳定性：不稳定
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            int j = i+1;
            for (; j < arr.length; j++) {
                // 遇到比i下标位置的元素小的就更新
                if (arr[minIndex] > arr[j]) minIndex = j;
            }
            // 走到这里j下标此时存放的就是数组中最小的元素
            swap(arr, i, minIndex);
        }
    }
    // 插入排序2
    // 过程：从中间的位置找到一个最小值，找到一个最大值，分别和arr[0] 交换，和 arr[arr.length - 1]交换
    // 但是此时需要注意的是可能arr[0] 就是数组中的最大值，左边和最小值交换玩之后就找不到
    // 最大值了，此时需要更正一下最大值的位置
    public static void selectSort2(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) minIndex = i;
                if (arr[i] > arr[maxIndex]) maxIndex = i;
            }
            swap(arr, minIndex, left);
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arr, maxIndex, right);
            left++;
            right--;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 堆排序
    // 过程：将数组建成一个对根堆，然后交换堆顶元素和最后一个位置的元素，此时最后一个位置的元素就是有序的了
    // 交换完之后就不是大根堆了，所以然后向下调整为大根堆，然后堆顶元素再和倒数第二个位置交换，循环上述操作
    // 时间复杂度：O（N * logN） 而且不管是有序还是无序的，都是这个时间复杂度
    public static void heapSort(int[] arr) {
        createBigHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr, 0, end);
            shiftDown(arr, 0, end);
            end--;
        }
    }

    private static void createBigHeap(int[] arr) {
        for (int parent = (arr.length - 1 - 1) / 2; parent >= 0; parent--) {
            int child = arr.length - 1;
            shiftDown(arr, parent, arr.length);
        }
    }
    private static void shiftDown(int[] arr, int parent, int len) {
        int child = 2 * parent + 1;
        // 也就是最起码要有左孩子
        while (child < len) {
            if (child + 1 < len && arr[child] < arr[child + 1]) child++;// 此时保证child中就是最大的
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    // 冒泡排序
    // 时间复杂度：O（N ^ 2）
    // 稳定性：稳定
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;// 优化
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j + 1);
                    flg = true;
                }
            }
            // 比如：第二趟排完序就有序了，第三趟一检查，发现有序了，就不用再继续排序了
            if (flg == false) {
                return;
            }
        }
    }

    // 快速排序
    // 过程：找一个基准值，找的过程中就以挖坑法的方式填坑，第一次排序以挖坑法填完坑之后，以基准值为界限，划分左边和右边
    // 划分完成之后继续以递归的方式挖坑然后划分，左边和右边，递归出口：当只有一个元素的时候结束
    /*
    * 时间复杂度：N * logN
    * 最好情况：N*log        最坏情况：N ^ 2(在数据有序 / 逆序的时候此时递归就是一颗单分支的树)
    * 空间复杂度：最好--logN    最坏：N（单分支的树）
    * 稳定性：不稳定
    * 所以快排在极端情况下，数据量很大，此时会栈溢出，
    * */
    public static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }
    private static void quick(int[] arr, int start, int end) {
        if (start >= end) return;

        // 使用这个优化主要是减少递归的次数
        if (end - start + 1 <= 14) {
            // 插入排序
            insertSort2(arr, start, end);
        }

        int index = midThree(arr, start, end);
        // 找到这个下标之后交换 start 和 index 位置的元素即可
        swap(arr, index, start);
        int pivot = partition2(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

    // 挖坑法
    private static int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            // 此时一定要取等号，否则会进入死循环
            while (left < right && arr[right] >= tmp) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) left++;
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

    // hoare 法
    private static int partition2(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;
        while (left < right) {
            while (left < right && arr[right] >= tmp) right--;
            while (left < right && arr[left] <= tmp) left++;
            swap(arr, left, right);
        }
        swap(arr, left, i);
        return left;
    }

    // 快排优化：三数取中
    private static int midThree(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) return left;
            else if (arr[mid] > arr[right]) return right;
            else return mid;
        } else {
            if (arr[mid] > arr[left]) return left;
            else if (arr[mid] < arr[right]) return right;
            else return mid;
        }
    }

    // 进一步优化：当递归到只剩下后两层的节点时，此时这部分剩下的数据已经接近有序了，所以此时可以
    // 插入排序是最快的, 但是是区间内进行插入排序，所以要指定一个区间
    public static void insertSort2(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    // arr[j + 1] = tmp;
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    // 非递归实现快速排序
    /*
    * 过程：先找一次基准，找完之后将基准左边的 左右区间 和 右边的 左右区间 进栈，
    * 之后将分别弹出左右区间再去找基准，找的过程中需要判断当前基准的左右区间的元素格式是否 >= 2
    * （如果只有一个元素 / 没有元素，此时就不用排序了）*/
    public static void quickSort2(int[] arr) {
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = arr.length - 1;
        int pivot = partition(arr, left, right);
        // 左边有两个元素的情况
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 右边有两个元素的情况
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.poll();
            left = stack.poll();
            pivot = partition(arr, left, right);
            // 找完基准之后检查左右两边有否还有两个或以上的元素，如果有此时继续找进栈
            // 之后循环出栈再找基准
            // 左边有两个元素的情况
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            // 右边有两个元素的情况
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    // 归并排序
    /*
    * 过程：先将整个数组进行分解，一直到分解后子序列中只有一个元素，之后再进行合并
    * 在合并的过程中进行排序，先让子序列内有序，再让子序列间有序
    * */
    // 时间复杂度：N * logN
    // 空间复杂度：N
    // 稳定性：稳定
    // 稳定的排序有：插入，冒泡，归并； 其他的排序都是不稳定的
    public static void mergeSort(int[] arr) {
        mergeSortFun(arr, 0, arr.length - 1);
    }
    private static void mergeSortFun(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSortFun(arr, left, mid);
        mergeSortFun(arr, mid + 1, right);
        merge(arr, left, right, mid);
    }
    private static void merge(int[] arr, int start, int end, int mid) {
        int s1 = start;
        // int e1= mid;
        int s2 = mid + 1;
        // int e2 = end;
        int[] tmp = new int[end - start + 1];
        int k = 0; // 控制 tmp 数组的下标
        while (s1 <= mid && s2 <= end) {
            if (arr[s1] < arr[s2]) tmp[k++] = arr[s1++];
            else tmp[k++] = arr[s2++];
        }
        while (s1 <= mid) tmp[k++] = arr[s1++];
        while (s2 <= end) tmp[k++] = arr[s2++];
        // 合并有序了之后需要将tmp数组中的元素拷贝到原来的数组中去
        for (int i = 0; i < tmp.length; i++) {
            // 不是直接复制到原来的数组中，
            arr[i + start] = tmp[i];
        }
    }

    // 非递归实现快速排序
    // 分治的思想：先让两个两个有序，再让四个四个有序，最后让整个数组有序
    // 分组：如果是数组中每一个单位划分成一个区间，此时子区间就是有序的，然后合并成两个两个一组
    // 调用merge 方法，再两个两个合并，继续调用，最后让整个数组有序
    public static void mergeSort2(int[] arr) {
        int gap = 1;  // gap 就是每个子区间中有多少个元素
        while (gap < arr.length) {
            for (int i = 0; i < arr.length; i += gap * 2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                merge(arr, left, right, mid);
            }
            gap *= 2;
        }
    }

}

